Ch.3 Set Theory

Set Theory

set: collection of objects
$U$ is the set of "all" objects
Notation: $\{$ ${$ list of all elements of set $\}$ $}$ , often named
- e.g. $\{$ a,e,i,o,u $\},\mathbb{N}=\{1,2,3,...\},\{1,2,3,...,100\}$
alternate: $\{$ ${$ description of universe $|$ $∣$ condition $\}$ $}$
- $\{n\in\mathbb{N}\space|\space n\le100\}$
$a\in A$ : $a$ is in $A$ ; $a\not\in A$ : $a$ is not in $A$

Operations with Sets

intersection $\cap$ : $A\cap B=\{a\in U\space|\space a\in A\land a\in B\}$
union $\cup$ : $A\cup B=\{a\in U\space|\space a\in A\lor a\in B\}$
compliment $X^c$ : $A^c=\{a\in U\space|\space a\not\in A\}$
difference $\setminus$ : $A\setminus B=\{a\in U\space|\space a\in A\land a\not\in B\}$
subset $\subseteq$ : $A\subseteq B=\{a\in U\space|\space a\in A\implies a\in B\}$

Given sets $X$ and $Y$ :
Proving $X\subseteq Y$ : check $\forall a(a\in X\implies a\in Y)$
Proving $X=Y$ : check $\forall a(a\in X\iff a\in Y)$

$U$ : "universe"- all sets $A$ are subsets of $U$
$\empty$ : empty set- $\empty\subseteq A$ for all $A$
$P(A)$ : power of a set- $\{S\subseteq U\space|\space S\subseteq A\}$ - "set of sets" (includes $\empty$ and $A$ )
$A\times B$ : cartesian product of two sets- $A\times B=\{(a,b)\space|\space a\in A\land b\in B\}$ ; is an ordered pair

Example 3.1

$S=\{\mathbb{N},\mathbb{Q},\mathbb{R},\mathbb{Z}\}\\A=\{\text{a,e,i,o,u}\}\\B=\{\text{a,b,c}\}\\C=\{0,1\}$

$\mathbb{N}\subseteq S\rightarrow$ $N \subseteq S \to$ false
- $\mathbb{N}\in S$
$\{\empty, \mathbb{R}\}\subseteq S\rightarrow$ false
$\{\text{a,e,o}\}\in P(A)\rightarrow$ true
$B\times C=\{(\text{a},0),(\text{a},1),(\text{b},0),(\text{b},1),(\text{c},0),(\text{c},1)\}\rightarrow$ true

Example 3.2

Show that $X\setminus Y=X\cap Y^c$ for any sets $X$ and $Y$

Two approaches: check all elements of left are elements of right, then all elements of right are elements of left; or use a series of equivalent statements

First check $X\setminus Y\subseteq X\cap Y^c$
Take $a\in X\setminus Y$ . By definition, $a\in X\land A\not\in Y$ . By definition of compliment, $a\in X\land A\in Y^c$ . Finally, by definition of intersection, $a\in X\cap Y^c$
Next check $X\cap Y^c\subseteq X\setminus Y$ (omitted)

Since they are by definition, we can go both ways with equivalent statements: $a\in X\setminus Y\iff a\in X\land a\not\in Y$ by definition, therefore it goes both ways.